深入剖析区块链的共识算法 Raft & PBFT

导语：区块链技术中，共识算法是其中核心的一个组成部分，比特币使用的是POW（Proof of Work，工作量证明），以太币将来使用POS（Proof of Stake，权益证明）。对于不需要货币体系的联盟链或者私链而言，传统的一致性算法成为首选，常见的有：PBFT（拜占庭容错）、PAXOS、RAFT。本文将详细阐述私链的raft算法和联盟链的PBFT算法，从算法的基本流程切入，深入介绍PBFT算法，并对比分析raft算法和PBFT算法的区别。

作者简介：梁敏鸿，美图区块链架构师，专注于区块链技术研究与产品应用落地。

区块链技术中，共识算法是其中核心的一个组成部分。首先我们来思考一个问题：什么是共识？对于现实世界，共识就是一群人对一件或者多件事情达成一致的看法或者协议。那么在计算机世界当中，共识是什么呢？

我的理解包含两个层面，第一个层面是点的层面，即多个节点对某个数据达成一致共识。第二个层面是线的层面，即多个节点对多个数据的顺序达成一致共识。这里的节点可以是任意的计算机设备，比如pc电脑，笔记本，手机，路由器等，这里的数据可以是交易数据，状态数据等。其中对数据顺序达成一致共识是很多共识算法要解决的本质问题。

常见的共识算法都有哪些呢？现阶段的共识算法主要可以分成三大类：公链，联盟链和私链。下面描述这三种类别的特征。

私链：私链的共识算法即区块链这个概念还没普及时的传统分布式系统里的共识算法，比如zookeeper的zab协议，就是类paxos算法的一种。私链的适用环境一般是不考虑集群中存在作恶节点，只考虑因为系统或者网络原因导致的故障节点。

联盟链：联盟链中，经典的代表项目是Hyperledger组织下的Fabric项目，Fabric0.6版本使用的就是pbft算法。联盟链的适用环境除了需要考虑集群中存在故障节点，还需要考虑集群中存在作恶节点。对于联盟链，每个新加入的节点都是需要验证和审核的。

公链：公链不仅需要考虑网络中存在故障节点，还需要考虑作恶节点，这一点和联盟链是类似的。和联盟链最大的区别就是，公链中的节点可以很自由的加入或者退出，不需要严格的验证和审核。

本文接下来将会主要阐述私链的raft算法和联盟链的pbft算法，以及它们的区别和对比。

【一．raft算法】

因为网上已经有大量文章对raft算法进行过详细的介绍，因此这部分只会简单的阐述算法的基本原理和流程。raft算法包含三种角色，分别是：跟随者（follower），候选人（candidate）和领导者（leader）。集群中的一个节点在某一时刻只能是这三种状态的其中一种，这三种角色是可以随着时间和条件的变化而互相转换的。

raft算法主要有两个过程：一个过程是领导者选举，另一个过程是日志复制，其中日志复制过程会分记录日志和提交数据两个阶段。raft算法支持最大的容错故障节点是（N-1）/2，其中N为 集群中总的节点数量。

国外有一个动画介绍raft算法介绍的很透彻，链接地址在这里[1]。这个动画主要包含三部分内容，第一部分介绍简单版的领导者选举和日志复制的过程，第二部分内容介绍详细版的领导者选举和日志复制的过程，第三部分内容介绍的是如果遇到网络分区（脑裂），raft算法是如何恢复网络一致的。有兴趣的朋友可以结合这个动画来更好的理解raft算法。

【二．pbft算法】

pbft算法的提出主要是为了解决拜占庭将军问题。什么是拜占庭将军问题呢？拜占庭位于如今的土耳其的伊斯坦布尔，是古代东罗马帝国的首都。拜占庭罗马帝国国土辽阔，为了达到防御目的，每块封地都驻扎一支由将军统领的军队，每个军队都分隔很远，将军与将军之间只能靠信差传递消息。 在战争的时候，拜占庭军队内所有将军必需达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定影响将军们达成一致共识。在已知有将军是叛徒的情况下，其余忠诚的将军如何达成一致协议的问题，这就是拜占庭将军问题。 

要让这个问题有解，有一个十分重要的前提，那就是信道必须是可靠的。如果信道不能保证可靠，那么拜占庭问题无解。关于信道可靠问题，会引出两军问题。两军问题的结论是，在一个不可靠的通信链路上试图通过通信以达成一致是基本不可能或者十分困难的。

那么如果在信道可靠的情况下，要如何解这个问题呢？拜占庭将军问题其实有很多种解法，接下来先介绍两位大牛，这两位大牛都在解决拜占庭问题上做出了突出的贡献。

如上图所示，拜占庭将军问题最早是由Leslie Lamport与另外两人在1982年发表的论文《The Byzantine Generals Problem 》提出的， 他证明了在将军总数大于3f ，背叛者为f 或者更少时，忠诚的将军可以达成命令上的一致，即3f+1<=n。算法复杂度为o（n^(f+1))。而Miguel Castro (卡斯特罗)和Barbara Liskov（利斯科夫）在1999年发表的论文《Practical Byzantine Fault Tolerance》中首次提出pbft算法，该算法容错数量也满足3f+1<=n,算法复杂度为o（n^2）。

网上关于pbft的算法介绍基本上是基于liskov在1999年发表的论文《Practical Byzantine Fault Tolerance》来进行解释的。当前网上介绍pbft的中文文章不算太多，基本上只有那几篇，并且感觉有些关键点解释得不够清晰，因此接下来会详细描述下pbft算法的过程和原理。

2.1 推论：raft算法的2f+1<=n和pbft的3f+1<=n

首先我们先来思考一个问题，为什么pbft算法的最大容错节点数量是（n-1）/3，而raft算法的最大容错节点数量是（n-1）/2？

对于raft算法，raft算法的的容错只支持容错故障节点，不支持容错作恶节点。什么是故障节点呢？就是节点因为系统繁忙、宕机或者网络问题等其它异常情况导致的无响应，出现这种情况的节点就是故障节点。那什么是作恶节点呢？作恶节点除了可以故意对集群的其它节点的请求无响应之外，还可以故意发送错误的数据，或者给不同的其它节点发送不同的数据，使整个集群的节点最终无法达成共识，这种节点就是作恶节点。

raft算法只支持容错故障节点，假设集群总节点数为n，故障节点为f，根据小数服从多数的原则，集群里正常节点只需要比f个节点再多一个节点，即f+1个节点，正确节点的数量就会比故障节点数量多，那么集群就能达成共识。因此raft算法支持的最大容错节点数量是（n-1）/2。

对于pbft算法，因为pbft算法的除了需要支持容错故障节点之外，还需要支持容错作恶节点。假设集群节点数为N，有问题的节点为f。有问题的节点中，可以既是故障节点，也可以是作恶节点，或者只是故障节点或者只是作恶节点。那么会产生以下两种极端情况：

第一种情况，f个有问题节点既是故障节点，又是作恶节点，那么根据小数服从多数的原则，集群里正常节点只需要比f个节点再多一个节点，即f+1个节点，确节点的数量就会比故障节点数量多，那么集群就能达成共识。也就是说这种情况支持的最大容错节点数量是（n-1）/2。

第二种情况，故障节点和作恶节点都是不同的节点。那么就会有f个问题节点和f个故障节点，当发现节点是问题节点后，会被集群排除在外，剩下f个故障节点，那么根据小数服从多数的原则，集群里正常节点只需要比f个节点再多一个节点，即f+1个节点，确节点的数量就会比故障节点数量多，那么集群就能达成共识。所以，所有类型的节点数量加起来就是f+1个正确节点，f个故障节点和f个问题节点，即3f+1=n。

结合上述两种情况，因此pbft算法支持的最大容错节点数量是（n-1）/3。下图展示了论文里证明pbft算法为什么3f+1<=n的一段原文，以及根据原文提到的两种情况对应的示意图。

3f+1<=n这个结论在pbft算法的流程中会大量使用到，因此在介绍pbft算法流程前先解释下这个推论。

2.2 算法基本流程

pbft算法的基本流程主要有以下四步：

1. 客户端发送请求给主节点

2. 主节点广播请求给其它节点，节点执行pbft算法的三阶段共识流程。

3. 节点处理完三阶段流程后，返回消息给客户端。

4. 客户端收到来自f+1个节点的相同消息后，代表共识已经正确完成。

为什么收到f+1个节点的相同消息后就代表共识已经正确完成？从上一小节的推导里可知，无论是最好的情况还是最坏的情况，如果客户端收到f+1个节点的相同消息，那么就代表有足够多的正确节点已全部达成共识并处理完毕了。

2.3 算法核心三阶段流程

   下面介绍pbft算法的核心三阶段流程，如下图所示：

 算法的核心三个阶段分别是pre-prepare阶段（预准备阶段），prepare阶段（准备阶段），commit阶段（提交阶段）。图中的C代表客户端，0，1，2，3代表节点的编号，打叉的3代表可能是故障节点或者是问题节点，这里表现的行为就是对其它节点的请求无响应。0是主节点。整个过程大致是：

首先，客户端向主节点发起请求，主节点0收到客户端请求，会向其它节点发送pre-prepare消息，其它节点就收到了pre-prepare消息，就开始了这个核心三阶段共识过程了。

Pre-prepare阶段：节点收到pre-prepare消息后，会有两种选择，一种是接受，一种是不接受。什么时候才不接受主节点发来的pre-prepare消息呢？一种典型的情况就是如果一个节点接到了一条pre-pre消息，消息里的v和n在之前收到里的消息是曾经出现过的，但是d和m却和之前的消息不一致，或者请求编号不在高低水位之间（高低水位的概念在2.4节会进行解释），这时候就会拒绝请求。拒绝的逻辑就是主节点不会发送两条具有相同的v和n，但d和m却不同的消息。

Prepare阶段：节点同意请求后会向其它节点发送prepare消息。这里要注意一点，同一时刻不是只有一个节点在进行这个过程，可能有n个节点也在进行这个过程。因此节点是有可能收到其它节点发送的prepare消息的。在一定时间范围内，如果收到超过2f个不同节点的prepare消息，就代表prepare阶段已经完成。

Commit阶段：于是进入commit阶段。向其它节点广播commit消息，同理，这个过程可能是有n个节点也在进行的。因此可能会收到其它节点发过来的commit消息，当收到2f+1个commit消息后（包括自己），代表大多数节点已经进入commit阶段，这一阶段已经达成共识，于是节点就会执行请求，写入数据。

 处理完毕后，节点会返回消息给客户端，这就是pbft算法的全部流程。

为了更清晰的展现这个过程和一些细节，下面以流程图来表示这个过程。

注解：

V：当前视图的编号。视图的编号是什么意思呢？比如当前主节点为A，视图编号为1，如果主节点换成B，那么视图编号就为2.这个概念和raft的term任期是很类似的。

N：当前请求的编号。主节点收到客户端的每个请求都以一个编号来标记。

M：消息的内容

d或D（m）：消息内容的摘要

 i： 节点的编号

2.4 checkpoint、stable checkpoint和高低水位

什么是checkpoint呢？checkpoint就是当前节点处理的最新请求序号。前文已经提到主节点收到请求是会给请求记录编号的。比如一个节点正在共识的一个请求编号是101，那么对于这个节点，它的checkpoint就是101.

那什么是stable checkpoint（稳定检查点）呢？stable checkpoint就是大部分节点（2f+1）已经共识完成的最大请求序号。比如系统有4个节点，三个节点都已经共识完了的请求编号是213.那么这个213就是stable checkpoint了。

那设置这个stable checkpoint有什么作用呢？最大的目的就是减少内存的占用。因为每个节点应该记录下之前曾经共识过什么请求，但如果一直记录下去，数据会越来越大，所以应该有一个机制来实现对数据的删除。那怎么删呢？很简单，比如现在的稳定检查点是213，那么代表213号之前的记录已经共识过的了，所以之前的记录就可以删掉了。

那什么是高低水位呢？下面以一个示意图来进行解释。

图中A节点的当前请求编号是1039，即checkpoint为1039，B节点的checkpoint为1133.当前系统stable checkpoint为1034.那么1034这个编号就是低水位，而高水位H=低水位h+L，其中L是可以设定的数值。因此图中系统的高水位为1034+100=1134。

举个例子：如果B当前的checkpoint已经为1034，而A的checkpoint还是1039，假如有新请求给B处理时，B会选择等待，等到A节点也处理到和B差不多的请求编号时，比如A也处理到1112了，这时会有一个机制更新所有节点的stabel checkpoint ，比如可以把stabel checkpoint设置成1100，于是B又可以处理新的请求了，如果L保持100不变，这时的高水位就会变成1100+100=1200了。

2.5 ViewChange（视图更改）事件

当主节点挂了（超时无响应）或者从节点集体认为主节点是问题节点时，就会触发ViewChange事件，ViewChange完成后，视图编号将会加1。

下图展示ViewChange的三个阶段流程。

如图所示，viewchange会有三个阶段，分别是view-change，view-change-ack和new-view阶段。从节点认为主节点有问题时，会向其它节点发送view-change消息，当前存活的节点编号最小的节点将成为新的主节点。当新的主节点收到2f个其它节点的view-change消息，则证明有足够多人的节点认为主节点有问题，于是就会向其它节点广播

New-view消息。注意：从节点不会发起new-view事件。对于主节点，发送new-view消息后会继续执行上个视图未处理完的请求，从pre-prepare阶段开始。其它节点验证new-view消息通过后，就会处理主节点发来的pre-prepare消息，这时执行的过程就是前面描述的pbft过程。到这时，正式进入 v+1（视图编号加1）的时代了。

为了更清晰的展现ViewChange这个过程和一些细节，下面以流程图来表示这个过程。

上图里红色字体部分的O集合会包含哪些pre-prepare消息呢？假设O集合里消息的编号范围：（min～max），则Min为V集合最小的stable checkpoint，Max为V集合中最大序号的prepare消息。最后一步执行O集合里的pre-preapare消息，每条消息会有两种情况: 如果max-min>0,则产生消息<pre-prepare,v+1,n,d> ；如果max-min=0，则产生消息<pre-prepare,v+1,n,d(null)>。

【三．raft和pbft的对比】

下图列出了raft算法和pbft算法在适用环境，通信复杂度，最大容错节点数和流程上的对比。

关于两个算法的适用环境和最大容错节点数，前文已经做过阐述，这里不再细说。而对于算法通信复杂度，为什么raft是o（n），而pbft是o（n^2）呢？这里主要考虑算法的共识过程。

对于raft算法，核心共识过程是日志复制这个过程，这个过程分两个阶段，一个是日志记录，一个是提交数据。两个过程都只需要领导者发送消息给跟随者节点，跟随者节点返回消息给领导者节点即可完成，跟随者节点之间是无需沟通的。所以如果集群总节点数为 n，对于日志记录阶段，通信次数为n-1，对于提交数据阶段，通信次数也为n-1，总通信次数为2n-2，因此raft算法复杂度为O（n）。

对于pbft算法，核心过程有三个阶段，分别是pre-prepare（预准备）阶段，prepare（准备）阶段和commit（提交）阶段。对于pre-prepare阶段，主节点广播pre-prepare消息给其它节点即可，因此通信次数为n-1；对于prepare阶段，每个节点如果同意请求后，都需要向其它节点再 广播parepare消息，所以总的通信次数为n*（n-1），即n^2-n；对于commit阶段，每个节点如果达到prepared状态后，都需要向其它节点广播commit消息，所以总的通信次数也为n*（n-1），即n^2-n。所以总通信次数为（n-1）+（n^2-n）+（n^2-n），即2n^2-n-1，因此pbft算法复杂度为O（n^2）。

流程的对比上，对于leader选举这块，raft算法本质是谁快谁当选，而pbft算法是按编号依次轮流做主节点。对于共识过程和重选leader机制这块，为了更形象的描述这两个算法，接下来会把raft和pbft的共识过程比喻成一个团队是如何执行命令的过程，从这个角度去理解raft算法和pbft的区别。

一个团队一定会有一个老大和普通成员。对于raft算法，共识过程就是：只要老大还没挂，老大说什么，我们（团队普通成员）就做什么，坚决执行。那什么时候重新老大呢？只有当老大挂了才重选老大，不然生是老大的人，死是老大的鬼。

对于pbft算法，共识过程就是：老大向我发送命令时，当我认为老大的命令是有问题时，我会拒绝执行。就算我认为老大的命令是对的，我还会问下团队的其它成员老大的命令是否是对的，只有大多数人（2f+1）都认为老大的命令是对的时候，我才会去执行命令。那什么时候重选老大呢？老大挂了当然要重选，如果大多数人都认为老大不称职或者有问题时，我们也会重新选择老大。

【四．结语】

raft算法和pbft算法是私链和联盟链中经典的共识算法，本文主要介绍了raft和pbft算法的流程和区别。raft和pbft算法有两点根本区别：

1. raft算法从节点不会拒绝主节点的请求，而pbft算法从节点在某些情况下会拒绝主节点的请求 ;

2. raft算法只能容错故障节点，并且最大容错节点数为（n-1）/2，而pbft算法能容错故障节点和作恶节点，最大容错节点数为（n-1）/3。

本文没有涉及算法正确性和收敛性的证明，从算法设计的角度来讲，是需要做这两方面工作的。

文中链接：

[1]http://thesecretlivesofdata.com/raft/

相关阅读：

活动预告：

6 月 1 ~ 2 日，GIAC 全球互联网架构大会将于深圳举行。GIAC 是高可用架构技术社区推出的面向架构师、技术负责人及高端技术从业人员的技术架构大会。今年的 GIAC 已经有腾讯、阿里巴巴、百度、今日头条、科大迅飞、新浪微博、小米、美图、Oracle、链家、唯品会、京东、饿了么、美图点评、罗辑思维、ofo、LinkedIn, Pivotal 等公司专家出席。

本期 GIAC 大会上，区块链部分精彩的议题如下：

参加 GIAC，盘点2018最新技术。点击“阅读原文”了解大会更多详情。